﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithm.Struct
{
    /// <summary>
    /// 两个定点之间不允许出现一条以上的连线
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Graph<T> :ICloneable where T :GraphNode
    {
        private List<T> _nodes= new List<T>();
        public IList<T> Nodes
        {
            get
            {
                 return _nodes.ToList().AsReadOnly();
            }
        }

        private List<GraphEdge> _edges = new List<GraphEdge>();
        public IList<GraphEdge> Edges
        {
            get
            {
                return _edges.ToList().AsReadOnly();
            }
        }

        public string Name
        {
            get;
            private set;
        }

        public T this[int index]
        {
            get
            {
                return _nodes[index];
            }
            set
            {
                _nodes[index] = value;
            }
        }

        private bool _isDir;
        public bool IsDirect
        {
            get
            {
                return _isDir;
            }
        }

        public Graph(string name,bool isDir)
        {
            this.Name = name;
            this._isDir = isDir;
        }

        public void AddNode(T node)
        {
            if (!this._nodes.Contains(node))
            {
                this._nodes.Add(node);
            }
        }

        public void AddEdge(GraphEdge edge)
        {
            this.AddNode((T)edge.FirstNode);
            this.AddNode((T)edge.SecondNode);
            edge.IsDirect = this.IsDirect;
            var exit = this._edges.Any((e) => { return e.Equals(edge); });
            if (!exit)
            {
                this._edges.Add(edge);
            }
        }

        public GraphEdge GetEdge(GraphNode node1,GraphNode node2)
        {
            if (IsDirect)
            {
                return node1.GetOutEdgeTo(this, node2);
            }
            else
            {
                return node1.GetEdgeWith(this, node2);
            }
        }

        public Graph<T> Transpose()
        {
            Graph<T> result = (Graph<T>) this.Clone();
            foreach (var e in result._edges)
            {
                var tmp = e.FirstNode;
                e.FirstNode = e.SecondNode;
                e.SecondNode = tmp;
            }
            return result;
        }

        public void Transpose1()
        {
            foreach (var e in this._edges)
            {
                var tmp = e.FirstNode;
                e.FirstNode = e.SecondNode;
                e.SecondNode = tmp;
            }
        }

        public object Clone()
        {
            Graph<T> result = new Graph<T>(this.Name,this.IsDirect);

            var tmpListNodes = new List<T>();

            for(int i=0;i<this._nodes.Count;i++)
            {
                tmpListNodes.Add((T)this._nodes[i].Clone());
            }

            foreach (var v in tmpListNodes)
            {
                result.AddNode(v);
            }
            List<GraphEdge> edges = new List<GraphEdge>();
            foreach (var e in this._edges)
            {
                var etmp = new GraphEdge();
                etmp.FirstNode =result._nodes[this._nodes.IndexOf((T)e.FirstNode)];
                etmp.SecondNode = result._nodes[this._nodes.IndexOf((T)e.SecondNode)];
                etmp.Weight = e.Weight;
                etmp.IsDirect = e.IsDirect;
                edges.Add(etmp);
            }

            foreach (var v in edges)
            {
                result.AddEdge(v);
            }
            
            return result;
        }
    }

    /// <summary>
    /// node 不能在链表中复用，因为weight 不能重复
    /// </summary>

    public static class GrapHelper
    {

        /// <summary>
        /// 要求权值非负值
        /// </summary>
        public static void Dijkstra<Value>(Graph<GraphNode> graph, GraphNode s) where Value : struct
        {
            Initialize_Single_Source<Value>(graph, s);
            bool[] visited = new bool[graph.Nodes.Count];
            int index = 0;
            for (int i = 0; i < graph.Nodes.Count -1; i++)
            {
                var min = double.MaxValue;
                for (int j = 0; j < graph.Nodes.Count; j++)
                {
                    var tmpNode = graph.Nodes[j] as GraphNode<Value>;
                    if (!visited[j]&& min > tmpNode.Dis)
                    {
                        min = tmpNode.Dis;
                        index = j;
                    }
                }
                visited[index] = true;
                var tmpNode1 = graph.Nodes[index] as GraphNode<Value>;
                var edges = tmpNode1.GetOutEdges(graph);
                foreach (var e in edges)
                {
                    Relax<Value>(graph, e.FirstNode, e.SecondNode);
                }
            }
        }

        /// <summary>
        /// 根据拓扑排序的顺序进行松弛获取单源最小路径
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="graph"></param>
        /// <param name="s"></param>
        public static void Dag_Shortest__Paths<Value>(Graph<GraphNode> graph, GraphNode s) where Value : struct
        {
            var topolo = Topological_Sort<Value>(graph);
            for (int i = 0; i < topolo.Count; i++)
            {
                var edges = topolo[i].GetOutEdges(graph);
                foreach (var e in edges)
                {
                    Relax<Value>(graph, e.FirstNode, e.SecondNode);
                }
            }
        }

        /// <summary>
        /// 松弛技术获取单源最小路径
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="graph"></param>
        /// <param name="s"></param>
        /// <returns></returns>
        public static bool Bellman_Ford<Value>(Graph<GraphNode> graph, GraphNode s) where Value : struct
        {
            Initialize_Single_Source<Value>(graph, s);
            for (int i = 0; i < graph.Nodes.Count - 1; i++)
            {
                foreach (var e in graph.Edges)
                {
                    Relax<Value>(graph, e.FirstNode, e.SecondNode);
                }
            }
            foreach (var e in graph.Edges)
            {
                var nodeV = e.SecondNode as GraphNode<Value>;
                var nodeU = e.FirstNode as GraphNode<Value>;
                if (nodeV.Dis > nodeU.Dis + e.Weight)
                {
                    return false;
                }
            }
            return true;
        }

        public static void Initialize_Single_Source<Value>(Graph<GraphNode> graph, GraphNode s) where Value : struct
        {
            foreach(var v in graph.Nodes)
            {
                var tmp = v as GraphNode<Value>;
                tmp.Dis = double.PositiveInfinity;
                tmp.P = null;
            }

            GraphNode<Value> root = s as GraphNode<Value>;

            root.Dis = 0;
        }

        public static void Relax<Value>(Graph<GraphNode> graph,GraphNode u, GraphNode v) where Value : struct
        {
            var tempV = v as GraphNode<Value>;
            var tempU = u as GraphNode<Value>;
            var edge = graph.GetEdge(u,v);

            if (tempV.Dis > tempU.Dis + edge.Weight)
            {
                tempV.Dis = tempU.Dis + edge.Weight;
                tempV.P = tempU;
            }
        }

        public static List<GraphEdge> MST_KRUSKAL<Value>(Graph<GraphNode> graph) where Value : struct
        {

            foreach (var v in graph.Nodes)
            {
                GraphNode<Value> tmp = v as GraphNode<Value>;
                tmp.NodeSet = new object();
            }
            var tmpresult = graph.Edges.OrderBy((e) => { return  e.Weight; });

            List<GraphEdge> result = new List<GraphEdge>();
            foreach (var e in tmpresult)
            {
                var f= e.FirstNode as GraphNode<Value>;
                var s =e.SecondNode as GraphNode<Value>;
                if (f.NodeSet != s.NodeSet)
                {
                    result.Add(e);
                    Unit<Value>(graph, f, s);
                }
            }

            return result;
        }

        private static void Unit<Value>(Graph<GraphNode> grap, GraphNode node1, GraphNode node2) where Value : struct
        {
            var n1 = grap.Nodes.Where((n) => { return (n as GraphNode<Value>).NodeSet == (node1 as GraphNode<Value>).NodeSet; });
            var n2 = grap.Nodes.Where((n) => { return (n as GraphNode<Value>).NodeSet == (node2 as GraphNode<Value>).NodeSet; });
            object o = new object();
            n1.ToList().ForEach((n) => { (n as GraphNode<Value>).NodeSet = o; });
            n2.ToList().ForEach((n) => { (n as GraphNode<Value>).NodeSet = o; });
        }

        /// <summary>
        /// 有向图使用的函数，获取强联通分支
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="rgraph"></param>
        public static void Strong_Connected_Components<Value>(Graph<GraphNode> graph) where Value:struct
        {
            DFS<Value>(graph);
            graph.Transpose1();
            graph.Nodes.OrderBy((node) => { return int.MaxValue - (node as GraphNode<Value>).SecondFindTime; });
            DFS<Value>(graph);
        }

        /// <summary>
        /// 多无环有向图进行拓扑排序
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="graph"></param>
        /// <returns></returns>
        public static List<GraphNode> Topological_Sort<Value>(Graph<GraphNode> graph) where Value:struct
        {
            DFS<Value>(graph);
            var result = graph.Nodes.OrderBy((node) => { return int.MaxValue - (node as GraphNode<Value>).SecondFindTime; }).ToList();
            return result;
        }



        /// <summary>
        /// 广度优先算法 该算法之后得到的图，节点被标了颜色、从s 到 该节点的距离等
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="graph"></param>
        /// <param name="s"></param>
        /// <param name="queueMaxLen"></param>
        public static void BFS<Value>(Graph<GraphNode> graph,GraphNode<Value> s,int queueMaxLen=500) where Value:struct
        {
            List<GraphNode<Value>> sLst = new List<GraphNode<Value>>();
            sLst.Add(s);
            List<GraphNode> nodes = graph.Nodes.Except(sLst).ToList();
            foreach (var n in nodes)
            {
                var tmp = n as GraphNode<Value>;
                tmp.Color = GraphNodeColor.White;
                tmp.Dis = double.MaxValue;
                tmp.P = null;
            }

            s.Color = GraphNodeColor.Grey;
            s.Dis = 0;
            Queue<GraphNode<Value>> queue = new Queue<GraphNode<Value>>(queueMaxLen);

            queue.Enqueue(s);
            while (!queue.IsEmpty())
            {
                var tmp = queue.Dequeue();
                var edges = graph.IsDirect ? tmp.GetOutEdgesInunDir(graph).ToList() : tmp.GetAllEdges(graph);
                foreach (var e in edges)
                {
                    var tmpNode = e.SecondNode as GraphNode<Value>;
                    if (tmpNode.Color == GraphNodeColor.White)
                    {
                        tmpNode.Color = GraphNodeColor.Grey;
                        tmpNode.Dis = tmpNode.Dis + 1;
                        tmpNode.P = tmp;
                        queue.Enqueue(tmpNode);
                    }
                }
                tmp.Color = GraphNodeColor.Black;
            }
        }


        /// <summary>
        /// 获取到一个从to 到 from 的列表，如果需要可以颠倒顺序得到从 from 到 to 的列表
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="graph"></param>
        /// <param name="from"></param>
        /// <param name="to"></param>
        /// <returns></returns>
        public static List<GraphNode> GetPathByBfs<Value>(Graph<GraphNode> graph, GraphNode from, GraphNode to) where Value : struct
        {
            List<GraphNode> result = new List<GraphNode>();
            var tmpTo = to as GraphNode<Value>;
            if (from == to)
            {
                result.Add(from);
            }
            else if (null == tmpTo.P)
            {
                return null;
            }
            else
            {
                var path = GetPathByBfs<Value>(graph, from, tmpTo.P);
                if (null == path || path.Count == 0)
                {
                    return null;
                }
                else
                {
                    result.AddRange(path);
                    result.Add(tmpTo);
                }
            }
            return result;
        }

        /// <summary>
        /// 深度优先算法
        /// </summary>
        /// <typeparam name="Value"></typeparam>
        /// <param name="graph"></param>
        /// <param name="isDirectedGraph"></param>
        public static void DFS<Value>(Graph<GraphNode> graph) where Value : struct
        {
            foreach (var v in graph.Nodes)
            {
                var tmp = v as GraphNode<Value>;
                tmp.Color = GraphNodeColor.White;
                tmp.P = null;
            }
            int time = 0;
            foreach (var v in graph.Nodes)
            {
                var tmp = v as GraphNode<Value>;
                if (tmp.Color == GraphNodeColor.White)
                {
                    DFS_Visit(graph, tmp, ref time);
                }

            }
        }

        public static void DFS_Visit<Value>(Graph<GraphNode> graph,GraphNode<Value> node, ref int time) where Value : struct
        {
            node.Color = GraphNodeColor.Grey;
            time++;
            node.FirstFindTime = time;
            var edges = node.GetOutEdgesInunDir(graph as Graph<GraphNode>);
            var nodes = edges.Select((e) => { return e.SecondNode; });
            foreach (var n in nodes)
            {
                var tmp = n as GraphNode<Value>;
                if(tmp.Color == GraphNodeColor.White)
                {
                    tmp.P= node;
                    tmp.EdgeType = GrapEdgeType.TreeEdge;
                    DFS_Visit<Value>(graph,tmp,ref time);
                }
                else if (tmp.Color == GraphNodeColor.Grey)
                {
                    tmp.EdgeType = GrapEdgeType.BackEdge;
                }
                else if(graph.IsDirect)
                {
                    tmp.EdgeType = node.FirstFindTime < tmp.FirstFindTime ? GrapEdgeType.ForwarEdge : GrapEdgeType.CrossEdge;
                }
            }
            node.Color =  GraphNodeColor.Black;
            time++;
            node.SecondFindTime = time;
        }
    }

    public class GraphNode<TValue> : GraphNode,ICloneable,IComparable<GraphNode<TValue>> where TValue:struct
    {
        public TValue W;

        /// <summary>
        /// 广度优先使用
        /// </summary>
        public GraphNodeColor Color;
        public GraphNode<TValue> P;
        public double Dis;

        /// <summary>
        /// 深度优先使用
        /// </summary>
        public double FirstFindTime;
        public double SecondFindTime;
        public GrapEdgeType EdgeType;

        /// <summary>
        /// 最小生成树使用
        /// </summary>
        public object NodeSet;

        public new object Clone()
        {
            var result = new GraphNode<TValue>();
            result.Color = this.Color;
            result.P = this.P;
            result.Dis = this.Dis;
            result.FirstFindTime = this.FirstFindTime;
            result.SecondFindTime = this.SecondFindTime;
            result.EdgeType = this.EdgeType;
            result.W = this.W;
            result.NodeSet = this.NodeSet;

            return result;
        }

        public int CompareTo(GraphNode<TValue> other)
        {
            return this.Dis > other.Dis ? 1 : this.Dis == other.Dis ? 0 : 1;
        }
    }

    public class GraphEdgeWithWeight : GraphEdge,IEquatable<GraphEdgeWithWeight>
    {
        public bool Equals(GraphEdgeWithWeight other)
        {
 	        return base.Equals(other);
        }
    }

    public class GraphEdge :IEquatable<GraphEdge>
    {
        public bool IsDirect
        {
            get;
            set;
        }

        public GraphNode FirstNode
        {
            get;
            set;
        }

        public GraphNode SecondNode
        {
            get;
            set;
        }

        public double Weight;
    
        public bool Equals(GraphEdge other)
        {
 	        if(null == other)
            {
                return false;
            }
            else
            {
                bool isOk = false;
                isOk = this.FirstNode == other.FirstNode && this.SecondNode == other.SecondNode && this.Weight == other.Weight;
                if (!IsDirect)
                {
                    isOk |= this.FirstNode == other.SecondNode && this.SecondNode == other.FirstNode && this.Weight == other.Weight;
                }

                return isOk;
            }
        }
    }

    public class GraphNode:ICloneable
    {
        public double Weight;

        public object Clone()
        {
            return new GraphNode() { Weight =this.Weight,Id=this.Id };
        }

        public IEnumerable<GraphEdge> GetInEdges<Node>(Graph<Node> graph)where Node:GraphNode
        {
            if (graph.IsDirect)
            {
                return graph.Edges.Where((e) => { return e.SecondNode == this; }).ToList();
            }
            return null;
        }

        public IEnumerable<GraphEdge> GetOutEdges<Node>(Graph<Node> graph)where Node:GraphNode
        {
            if (graph.IsDirect)
            {
                return graph.Edges.Where((e) =>
                { 
                    return e.FirstNode == this; 
                }).ToList();
            }
            return null;
        }

        public GraphEdge GetOutEdgeTo<Node>(Graph<Node> graph,GraphNode node)where Node:GraphNode
        {
            var outNodes = this.GetOutEdges(graph);
            return outNodes.FirstOrDefault((n)=>{ return n.SecondNode==node; });
        }

        public GraphEdge GetInEdgeFrom<Node>(Graph<Node> graph,GraphNode node)where Node:GraphNode
        {
            var outNodes = this.GetInEdges(graph);
            return outNodes.FirstOrDefault((n)=>{ return n.FirstNode==node; });
        }

        public GraphEdge GetEdgeWith<Node>(Graph<Node> graph,GraphNode node) where Node:GraphNode
        {
            GraphEdge result = GetOutEdgeTo(graph,node);
            if(null != result)
            {
                return result;
            }
            result = GetInEdgeFrom(graph,node);

            return result;
        }

        public IEnumerable<GraphEdge> GetOutEdgesInunDir<Node>(Graph<Node> graph)where Node:GraphNode
        {
            return graph.Edges.Where((e) => { 
                return e.FirstNode == this;
            }).ToList();
        }

        public IEnumerable<GraphEdge> GetAllEdges<Node>(Graph<Node> graph)where Node:GraphNode
        {
            return graph.Edges.Where((e) =>
            { 
                return e.FirstNode == this || e.SecondNode == this;
            }).ToList();
        }

        public int Id;
    }

    public enum GrapEdgeType
    {
        //有向图和无向图都会出现
        TreeEdge,
        BackEdge,

        //这两种在有向图中出现
        ForwarEdge,
        CrossEdge
    }
    public enum GraphNodeColor
    {
        White,
        Grey,
        Black
    }
}
